import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class PathFind {
	private static PathFind instance;
	
	private Ants worldState;

	private static float alpha = 0.75f;
	private static float beta = 0.75f;
	
	private static float mean;
	private static float deviation;
	
	private List<SearchNode> closed = new ArrayList<SearchNode>();
	private List<SearchNode> open = new ArrayList<SearchNode>();

	private List<Tile> neighbors = new ArrayList<Tile>();

	public static PathFind getSingleton() {
		if (instance == null)
			instance = new PathFind();
		
		return instance;
	}
	
	private PathFind() {
	}

	public List<Tile> findPath(Ants worldState, Tile start, Tile goal) {
		if (worldState.getTimeRemaining() < mean + 2*deviation)
			return null;
		
		long startTime = System.currentTimeMillis();
		
		List<Tile> route = AStar(worldState, start, goal);
		
		long endTime = System.currentTimeMillis();
		
		long dt = endTime - startTime;
		
		mean = alpha*mean + (1-alpha)*dt;
		deviation = beta*deviation + (1-beta)*Math.abs(mean-dt);
		
		return route;
	}
	
	private List<Tile> AStar(Ants worldState, Tile start, Tile goal) {
		this.worldState = worldState;

		closed.clear();
		open.clear();

		SearchNode startNode = new SearchNode(start, 0, 0, null);
		open.add(startNode);

		while (!open.isEmpty()) {
			SearchNode node = selectNodeWithLowestF(open);

			if (node.getPosition().equals(goal))
				return reconstructPath(node);

			open.remove(node);

			closed.add(node);

			for (Tile neighbor : getNodeNeighbors(node)) {
				if (findNode(closed, neighbor) == null) {
					int g = node.getG() + 1;

					SearchNode found = findNode(open, neighbor);
					if (found == null) {
						SearchNode newNode = new SearchNode(neighbor, g,
								manhattanDistance(neighbor, goal), node);

						open.add(newNode);
					} else if (g < found.getG()) {
						found.setParent(node);
						found.setG(g);
					}
				}
			}
		}

		return null;
	}

	private SearchNode findNode(List<SearchNode> list, Tile tile) {
		for (SearchNode node : list)
			if (node.getPosition().equals(tile))
				return node;

		return null;
	}

	private List<Tile> getNodeNeighbors(SearchNode node) {
		neighbors.clear();

		for (Aim direction : Aim.values()) {
			Tile neighbor = worldState.getTile(node.getPosition(), direction);
			if (worldState.getIlk(neighbor).isPassable() && !worldState.getMyHills().contains(neighbor))
				neighbors.add(neighbor);
		}

		return neighbors;
	}

	private List<Tile> reconstructPath(SearchNode goal) {
		List<Tile> path = new ArrayList<Tile>();
		SearchNode node = goal;

		while (node.getParent() != null) {
			path.add(node.getPosition());
			node = node.getParent();
		}

		Collections.reverse(path);

		return path;
	}

	private SearchNode selectNodeWithLowestF(List<SearchNode> open) {
		SearchNode result = new SearchNode();

		int currentDistance;
		int smallestDistance = Integer.MAX_VALUE;
		for (SearchNode node : open) {
			currentDistance = node.getF();

			if (currentDistance <= smallestDistance
					|| (currentDistance == smallestDistance && node.getG() > result
							.getG())) {
				result = node;
				smallestDistance = currentDistance;
			}
		}

		return result;
	}

	private int manhattanDistance(Tile node, Tile goal) {
		return (Math.abs(node.getRow() - goal.getRow()) + Math.abs(node
				.getCol() - goal.getCol()));
	}
}